package leetcode.array_sort;

/**
 * 215. 数组中的第K个最大元素
 * <p>
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * <p>
 * 示例 2:
 * <p>
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 * <p>
 * 说明:
 * <p>
 * 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
 * <p>
 * 如果我们从小到大排列，则第k大元素在 r-k上
 * 从大到小排 k 在 k-1 的位置上
 */
public class Solution215 {
    public static int findKthLargest(int[] nums, int k) {
        return qSort(nums, 0, nums.length - 1, k - 1);
    }

    private static int qSort(int[] arr, int l, int r, int k) {
//        判断递归到底的情况
        if (l >= r) {// 此时 l=k
            return arr[k];
        }
        //进行快排 第k大的元素在r-k索引上

//        随机选举一个元素作为v(int) (Math.random() * (r - l + 1) + l)
        int randomIndex = (int) (Math.random() * (r - l + 1) + l);
        swap(arr, l, randomIndex);
        int v = arr[l];

        //定义j 使得 arr[l+1,j] 存放比v小的元素  [j+1,i) 存放比v大的元素 从大到小排序反之    从大到小排序
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] > v) {
                j++;
                swap(arr, j, i);
            }
        }
        //j指向最后一个比v小的元素.
        swap(arr, l, j);
        //此时v元素已经是排好序的元素，在arr中的索引为 j  此时需要判断k与j位置关系  第k大的元素位置为l+1
        if (k == j) {
            return arr[j];
        } else if (k < j) {
            return qSort(arr, l, j - 1, k);
        } else {
            return qSort(arr, j + 1, r, k);
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums1 = {3, 2, 1, 5, 6, 4};

        System.out.println(findKthLargest(nums1, 2));
        System.out.println(selection(nums1, 2));
    }


    // 补充使用选择排序进行找出第k个最大元素  最坏情况沦为n2时间复杂度
    public static int selection(int[] nums, int k) {
        int i = 0;
        for (; i < k; i++) {
            int j = i + 1;
            for (; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                    swap(nums, i, j);
                }
            }
        }
        return nums[i - 1];
    }
}
